Việt Nam có chung đường biên giới dài 1.137km với Campuchia.[3] Trong lịch sử, đặc biệt là thời kỳ Nam tiến, Campuchia đã bị mất đất về tay Việt Nam và phải triều cống cho Việt Nam.[4] Vào thế kỉ XIX, cả 2 đều trở thành thuộc địa của thực dân Pháp và cùng với Lào tạo thành Đông Dương thuộc Pháp. Những nhà yêu nước của cả Việt Nam và Campuchia đã cùng cộng tác để chống Pháp trong chiến tranh Đông Dương (1945-1954) nhằm mục đích dành độc lập cho mỗi dân tộc[4], song lại bị những nhà dân tộc chủ nghĩa đối lập ở Campuchia, bao gồm vua tương lai Norodom Sihanouk, nghi ngờ là ý đồ thuộc địa hóa Campuchia của Việt Nam.

Trong những thời điểm này, nhà lãnh đạo Việt Nam là Chủ tịch Hồ Chí Minh và Quốc vương Campuchia Norodom Sihanouk đã có những bức điện trao đổi qua lại với những lời lẽ tốt đẹp. Quốc vương Campuchia đã đã gửi tặng thuốc cho Hồ Chí Minh. Khi Hồ Chí Minh mất, tháng 9/1969, ông Norodom Sihanouk cùng phu nhân đã tới Hà Nội dự Lễ Truy điệu. Tại đây, ông phát biểu: "Được nhân dân kính mến, được bạn hữu khâm phục, được kẻ thù tôn trọng, Hồ Chí Minh là một trong những nhân vật hoạt động chính trị và là lãnh tụ cao quý nhất của thế kỷ này... Trong thế giới tàn bạo này, Người đã đem lại cho chúng ta cũng như cho biết bao dân tộc khác những lý do để hy vọng.".[5]

Trong Chiến tranh Việt Nam, Mặt trận Dân tộc Giải phóng miền Nam Việt Nam đã sử dụng lãnh thổ của Campuchia - một nước trung lập, để phát động các cuộc tấn công vào miền Nam Việt Nam, cùng lúc với lực lượng Khmer Đỏ vốn đang là đồng minh Mặt trận Dân tộc Giải phóng miền Nam Việt Nam bấy giờ. Điều này đã dẫn tới việc Quân đội Hoa Kỳ và Quân lực Việt Nam Cộng Hòa phát động Chiến dịch Campuchia nhằm tiêu diệt lực lượng Quân Giải phóng hoạt động bí mật tại Campuchia.[6] Với sự rút lui của quân Mỹ và việc các Đảng Cộng sản giành thắng lợi ở Việt Nam và Campuchia năm 1975, cả 3 nước Đông Dương đều đi theo chế độ cộng sản.[4]. Sau khi kiểm soát toàn bộ lãnh thổ Campuchia, chế độ cộng sản Khmer Đỏ đã nhanh chóng quay sang thế đối đầu với chính phủ cộng sản Việt Nam do những vấn đề về tranh chấp lãnh thổ, điều này đã dẫn tới Chiến tranh Đông Dương lần 3 bốn năm sau đó.